home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
ftp.cs.arizona.edu
/
ftp.cs.arizona.edu.tar
/
ftp.cs.arizona.edu
/
icon
/
newsgrp
/
group93b.txt
/
000071_icon-group-sender _Tue May 4 03:01:03 1993.msg
< prev
next >
Wrap
Internet Message Format
|
1993-06-16
|
4KB
Received: by cheltenham.cs.arizona.edu; Sun, 9 May 1993 05:55:12 MST
Date: 4 May 93 03:01:03 GMT
From: portal!cup.portal.com!Eric-Amick@uunet.uu.net (Richard E Amick)
Organization: The Portal System (TM)
Subject: Re: Is this passable code?
Message-Id: <80791@cup.portal.com>
References: <9304260508.AA21290@internal.apple.com>
Sender: icon-group-request@cs.arizona.edu
To: icon-group@cs.arizona.edu
Status: R
Errors-To: icon-group-errors@cs.arizona.edu
>>I started using Icon recently, and am impressed with the
>>power of the language. But, since i'm learning on my own and
>>don't have experience with Icon, i don't know if i'm doing
>>things right. Recently i wrote a short program to find
>>anagrams (yeah...) using the unix dictionary. I'd appreciate
>>any comments/suggestions/flames, etc about my programming
>>style and the Icon way.
>
>I did think of a different (simpler, I believe) way of implementing the
>anagram algorithm, using sets. I don't know if it's better or worse, but
>it does illustrate my particular style for programming in Icon. Here it
>is, along with an explanation of some of my stylistic choices:
>
>
># look up anagrams of all the command line arguments in /usr/dict/words
>
>
>procedure main(LArguments)
>
>local SAnagrams
>local fWords
>local sWord
>
>SAnagrams := set()
>
>every insert(SAnagrams, Permute(map(!LArguments)))
>
>fWords := open("/usr/dict/words") |
> stop("Cannot open /usr/dict/words for reading; aborting.")
>
>while sWord := read(fWords) do {
> if member(SAnagrams, map(sWord)) then write(sWord)
>}
>
>close(fWords)
>
>
>end
>
>
>procedure Permute(sString)
>
>local iPos
>
>if 0 = *sString then return sString
>
>suspend sString[iPos := 1 to *sString] ||
> Permute(sString[1:iPos] || sString[iPos+1:0])
>
>end
>
>
>
[Lots of commentary about code deleted.]
>Variations on this algorithm: There are 24259 words in /usr/dict/words on
>my Unix machine. If I was expecting to process many words with 8 or more
>unique letters (8! = 40320 permutations), I would have approached this a
>little differently. I would have read /usr/dict/words into a set (or a
>table, if I thought that preserving case was important), and do something
>like [note: if you want to preserve case, it's actually a little harder
>than this. The algorithm below ignores words in /usr/dict/words that only
>differ by case, and it probably shouldn't]:
>
>
>
>procedure main(LArguments)
>
>local TWords
>local fWords
>local sWord
>
>TWords := table()
>
>fWords := open("/usr/dict/words") |
> stop("Cannot open /usr/dict/words for reading; aborting.")
>
>while sWord := read(fWords) do TWords[map(sWord)] := sWord
>
>close(fWords)
>
>
>every write(\TWords[Permute(map(!LArguments))])
>
>end
>
>
>
>I would probably even come up with a heuristic that analyses LArguments and
>determines which of the two above variations to call to do the work.
>
>
>I hope this is what you were looking for. I can't believe I wrote this
>much on a 20 line algorithm. :-) Comments are appreciated.
Allow me to propose a combination of the two which just might be faster.
Since virtually all of the permutations generated will not match
anything, perhaps you should consider the basic principle of anagrams:
all the letters are present in both, just in a different order. If we
put the letters of a word in a standard order, say, sorted
alphabetically, then the comparison will go much faster; surely sorting
is less work than generating 40,000 permutations. (Considering that
10-letter words produce about 4,000,000 permutations, this is a very
reasonable idea.) Build your table as before, but make the sorted
letters the key and the set of words with the same key the data
associated with it. I'm still in the novice stage with Icon myself, so
I'll let someone else do the coding. :-) (The algorithm comes from the
book "Programming Pearls" by Jon Bentley, much as I wish I had thought
of it myself.)
>___
>NEVIN ":-)" LIBER, Blue Meanie, Macintosh System Software
> email: nevin@apple.com paper: Apple Computer, Inc.
> voice: (408) 974-MIX1 2 Infinite Loop, MS: 302-4Q
> AppleLink: BADENOV Cupertino, CA 95014